﻿//-----------------------------------------------------------------------
// <copyright file="BreadthFirstSearch.cs" company="Luboš Bretschnieder">
// Copyright (c) 2008 Luboš Bretschnieder, Licensed under the Apache License, Version 2.0.
// </copyright>
//-----------------------------------------------------------------------
namespace Graphs.Algorithms
{
    using System;
    using System.Collections.Generic;
    using UI;
    using UI.StatusBars;

    /// <summary>
    /// Breadth-first search algorithm
    /// </summary>
    public class BreadthFirstSearch : IAlgorithm
    {
        /// <summary>List of steps.</summary>
        private List<AlgorithmStep> steps;

        /// <summary>Queue used in the algorithm.</summary>
        private Queue<Vertex> queue;

        /// <summary>List of processed edges.</summary>
        private List<Edge> processedEdges;

        /// <summary>List of processed vertices.</summary>
        private List<Vertex> processedVertices;

        /// <summary>
        /// Gets or sets the graph.
        /// </summary>
        /// <value>The graph.</value>
        public Graph Graph
        {
            private get;
            set;
        }

        /// <summary>
        /// Gets the steps of the algorithm execution.
        /// </summary>
        /// <value>The steps.</value>
        public List<AlgorithmStep> Steps
        {
            get { return this.steps; }
        }

        /// <summary>
        /// Executes the algorithm.
        /// </summary>
        public void Execute()
        {
            this.Execute(this.Graph.SortedVertices.Keys[0]);
        }

        /// <summary>
        /// Executes the algorithm starting in specified vertex.
        /// </summary>
        /// <param name="startVertexName">Name of the start vertex.</param>
        public void Execute(string startVertexName)
        {
            this.Reset();
            Vertex startVertex = this.Graph.GetVertex(startVertexName) ?? this.Graph.SortedVertices.Values[0];
            startVertex.State = VertexState.Blue;
            this.queue.Enqueue(startVertex);
            this.processedVertices.Add(startVertex);

            List<IStatusBar> statusBars = this.GetStatusBars();
            this.steps.Add(new AlgorithmStep(this.Graph.Clone(), statusBars));

            while (this.queue.Count > 0)
            {
                this.MakeStep();
            }
        }

        /// <summary>
        /// Resets the algorithm (normally should be called when executing algorithm).
        /// </summary>
        public void Reset()
        {
            this.steps = new List<AlgorithmStep>();
            this.queue = new Queue<Vertex>();
            this.processedEdges = new List<Edge>();
            this.processedVertices = new List<Vertex>();
        }

        /// <summary>
        /// Makes the algorithm step.
        /// </summary>
        private void MakeStep()
        {
            // find connected vertices
            Vertex lastVertex = this.queue.Peek();
            List<Vertex> connectedVertices = this.Graph.FindConnectedVertices(lastVertex, new List<Edge>());

            bool found = false;
            if (connectedVertices.Count > 0)
            {
                foreach (Vertex connectedVertex in connectedVertices)
                {
                    // find unprocessed vertex
                    Edge processedEdge = this.Graph.GetEdge(lastVertex, connectedVertex);
                    if (!this.processedVertices.Contains(connectedVertex))
                    {
                        // add to queue
                        this.queue.Enqueue(connectedVertex);
                        this.processedVertices.Add(connectedVertex);
                        connectedVertex.State = VertexState.Blue;

                        processedEdge.State = EdgeState.Blue;
                        this.processedEdges.Add(processedEdge);

                        found = true;
                        break;
                    }

                    if (!this.processedEdges.Contains(processedEdge))
                    {
                        processedEdge.State = EdgeState.Grey;
                    }
                }
            }

            if (!found)
            {
                // no unprocessed connected vertex found -> dequeue
                Vertex removedVertex = this.queue.Dequeue();
                removedVertex.State = VertexState.Red;
            }

            if (this.queue.Count == 0)
            {
                foreach (Edge processedEdge in this.processedEdges)
                {
                    if (processedEdge.State == EdgeState.Blue)
                    {
                        processedEdge.State = EdgeState.Red;
                    }
                }
            }

            List<IStatusBar> statusBars = this.GetStatusBars();
            this.steps.Add(new AlgorithmStep(this.Graph.Clone(), statusBars));
        }

        /// <summary>
        /// Gets the status bars.
        /// </summary>
        /// <returns>List of status bars</returns>
        private List<IStatusBar> GetStatusBars()
        {
            List<IStatusBar> statusBars = new List<IStatusBar>();

            List<Vertex> unprocessedVertices = this.GetUnprocessedVertices();
            VerticesStatusBar unprocessedVerticesStatusBar = new VerticesStatusBar { Label = "Unprocessed vertices", Vertices = unprocessedVertices };
            statusBars.Add(unprocessedVerticesStatusBar);

            VerticesStatusBar verticesStatusBar = new VerticesStatusBar { Label = "FIFO", Vertices = this.queue.ToArray() };
            statusBars.Add(verticesStatusBar);
            return statusBars;
        }

        /// <summary>
        /// Gets the unprocessed vertices.
        /// </summary>
        /// <returns>List of unprocessed vertices</returns>
        private List<Vertex> GetUnprocessedVertices()
        {
            List<Vertex> unprocessedVertices = new List<Vertex>();
            foreach (Vertex vertex in this.Graph.Vertices)
            {
                if (!this.processedVertices.Contains(vertex))
                {
                    unprocessedVertices.Add(vertex);
                }
            }

            return unprocessedVertices;
        }
    }
}
